package sort 
//这个版本的时间复杂度比较高不建议用
type HeapSortV1 struct {

}

func NewHeapSortV1() *HeapSortV1 {
	return &HeapSortV1{}
}

var nextLPos = func(i int) int {
	return i << 1 + 1;
} 

var nextRPos = func(i int) int {
	return i << 1 + 2
} 

func (h *HeapSortV1) Sort(nums []int) []int {
	for i := 0; i < len(nums) ; i++ {
		nums = h.BuildHeap(nums, len(nums) - i)
		nums[0], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[0]
	} 
	return nums 
}

func (h *HeapSortV1) BuildHeap(nums []int, r int) []int {
	lastRoot := r / 2 - 1
	for i := lastRoot; i >= 0; i -- {
		rightIdx , leftIdx := nextRPos(i), nextLPos(i)
		//检查右子树
		if rightIdx < r && nums[rightIdx] > nums[i] {
			rightRoot := nums[rightIdx]
			//先进行交换
			nums[rightIdx], nums[i] = nums[i], nums[rightIdx]
			//看左子树有没有受到影响
			rt , lt := nextRPos(rightIdx), nextLPos(rightIdx)
			if (lt < r && nums[lt] > rightRoot) || (rt < r && nums[rt] > rightRoot) {
				h.BuildHeap(nums, r)
			} 
		} 
		//检查左子树
		if leftIdx < r && nums[leftIdx] > nums[i] {
			leftRoot := nums[leftIdx]
			//先进行交换
			nums[leftIdx], nums[i] = nums[i], nums[leftIdx]
			//看右子树有没有受到影响
			rt , lt := nextRPos(leftIdx), nextLPos(leftIdx)
			if (lt < r && nums[lt] > leftRoot) || (rt < r && nums[rt] > leftRoot) {
				h.BuildHeap(nums, r)
			} 
		}
	}
	return nums 
}